import java.security.PublicKey;

class Solution {
    //解法1：
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) count++;
            if (nums[i] > target) break;
        }
        return count;
    }
    //解法2：二分法 解法二优先！！！！！！！！！！ 时间复杂度o(log2n)
    public int search2(int[] nums, int target) {
        return helper(nums,target) - helper(nums,target - 1);
    }
    public int helper(int[] nums,int tar) {
        int i = 0;
        int j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] <= tar) i = mid + 1;
            else j = mid - 1;
        }
        return i;
    }

}